//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[
//b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）： 
//
// 
// 0 <= a, b, c, d < n 
// a、b、c 和 d 互不相同 
// nums[a] + nums[b] + nums[c] + nums[d] == target 
// 
//
// 你可以按 任意顺序 返回答案 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,2,2,2,2], target = 8
//输出：[[2,2,2,2]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// -10⁹ <= nums[i] <= 10⁹ 
// -10⁹ <= target <= 10⁹ 
// 
//
// Related Topics 数组 双指针 排序 👍 1619 👎 0


package leetcode.editor.cn;

// [18]四数之和

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FourSum_18 {
    public static void main(String[] args) {
        Solution solution = new FourSum_18().new Solution();
        System.out.println(solution.fourSum(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            if (nums == null || nums.length < 4) {
                return new ArrayList<>();
            }
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            for (int a = 0; a < nums.length - 3; a++) {
                if (a != 0 && nums[a] == nums[a - 1]) {
                    continue;
                }
                for (int d = nums.length - 1; d > a + 2; d--) {
                    if (d != nums.length - 1 && nums[d] == nums[d + 1]) {
                        continue;
                    }
                    int r = d - 1;
                    for (int l = a + 1; l < d - 1; l++) {
                        if (l != a + 1 && nums[l] == nums[l - 1]) {
                            continue;
                        }
                        while ((long) nums[a] + nums[d] + nums[l] + nums[r] > target && r > l) {
                            r--;
                        }
                        if (l == r) {
                            break;
                        }
                        if ((long) nums[a] + nums[d] + nums[l] + nums[r] == target) {
                            Integer[] ints = {nums[a], nums[l], nums[r], nums[d]};
                            List<Integer> list = new ArrayList<>(ints.length);
                            Collections.addAll(list, ints);
                            ans.add(list);
                        }
                    }
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}